﻿// --------------------------------------------------------------------------------------------------------------------
// <copyright file="TreeBase.cs" company="Team Awesome">
//   Awesome
// </copyright>
// <summary>
//   Defines the LeftLeaningTreeBase type.
// </summary>
// --------------------------------------------------------------------------------------------------------------------

namespace System.Collections
{
    using Diagnostics.Contracts;
    using Generic;

    /// <summary>
    /// Contracts for left leaning trees.
    /// </summary>
    [ContractClass(typeof(TreeContract))]
    public abstract class TreeBase : ITree<int>
    {
        /// <summary>
        /// Gets or sets the tree's stamp. Is updated for every new item added.
        /// </summary>
        protected int ChangeStamp { get; set; }

        /// <summary>
        /// Check if the collection has been modified since a specified time, expressed as a stamp value.
        /// </summary>
        /// <exception cref="InvalidOperationException">
        /// if this collection has been updated 
        /// since a target time
        /// </exception>
        /// <param name="theStamp">
        /// The the Stamp.
        /// </param>
        public virtual void CheckModified(int theStamp)
        {
            if (ChangeStamp != theStamp)
                throw new InvalidOperationException("Collection was modified; enumeration operation may not execute.");
        }

        #region Implementation of ICollection<int>

        /// <summary>
        /// Gets the number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"/>.
        /// </summary>
        /// <returns>
        /// The number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"/>.
        /// </returns>
        public abstract int Count { get; }

        /// <summary>
        /// Gets a value indicating whether the <see cref="T:System.Collections.Generic.ICollection`1"/> is read-only.
        /// </summary>
        /// <returns>
        /// true if the <see cref="T:System.Collections.Generic.ICollection`1"/> is read-only; otherwise, false.
        /// </returns>
        public abstract bool IsReadOnly { get; }

        /// <summary>
        /// Adds an item to the <see cref="T:System.Collections.Generic.ICollection`1"/>.
        /// </summary>
        /// <param name="item">The object to add to the <see cref="T:System.Collections.Generic.ICollection`1"/>.</param><exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.ICollection`1"/> is read-only.</exception>
        public abstract void Add(int item);

        /// <summary>
        /// Removes all items from the <see cref="T:System.Collections.Generic.ICollection`1"/>.
        /// </summary>
        /// <exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.ICollection`1"/> is read-only. </exception>
        public abstract void Clear();

        /// <summary>
        /// Determines whether the <see cref="T:System.Collections.Generic.ICollection`1"/> contains a specific value.
        /// </summary>
        /// <returns>
        /// true if <paramref name="item"/> is found in the <see cref="T:System.Collections.Generic.ICollection`1"/>; otherwise, false.
        /// </returns>
        /// <param name="item">The object to locate in the <see cref="T:System.Collections.Generic.ICollection`1"/>.</param>
        public abstract bool Contains(int item);

        /// <summary>
        /// Copies the elements of the <see cref="T:System.Collections.Generic.ICollection`1"/> to an <see cref="T:System.Array"/>, starting at a particular <see cref="T:System.Array"/> index.
        /// </summary>
        /// <param name="array">The one-dimensional <see cref="T:System.Array"/> that is the destination of the elements copied from <see cref="T:System.Collections.Generic.ICollection`1"/>. The <see cref="T:System.Array"/> must have zero-based indexing.</param><param name="arrayIndex">The zero-based index in <paramref name="array"/> at which copying begins.</param><exception cref="T:System.ArgumentNullException"><paramref name="array"/> is null.</exception><exception cref="T:System.ArgumentOutOfRangeException"><paramref name="arrayIndex"/> is less than 0.</exception><exception cref="T:System.ArgumentException"><paramref name="array"/> is multidimensional.-or-The number of elements in the source <see cref="T:System.Collections.Generic.ICollection`1"/> is greater than the available space from <paramref name="arrayIndex"/> to the end of the destination <paramref name="array"/>.</exception>
        public abstract void CopyTo(int[] array, int arrayIndex);

        /// <summary>
        /// Removes the first occurrence of a specific object from the <see cref="T:System.Collections.Generic.ICollection`1"/>.
        /// </summary>
        /// <returns>
        /// true if <paramref name="item"/> was successfully removed from the <see cref="T:System.Collections.Generic.ICollection`1"/>; otherwise, false. This method also returns false if <paramref name="item"/> is not found in the original <see cref="T:System.Collections.Generic.ICollection`1"/>.
        /// </returns>
        /// <param name="item">The object to remove from the <see cref="T:System.Collections.Generic.ICollection`1"/>.</param><exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.ICollection`1"/> is read-only.</exception>
        public abstract bool Remove(int item);

        #endregion

        #region Implementation of IEnumerable

        /// <summary>
        /// Returns an enumerator that iterates through the collection.
        /// </summary>
        /// <returns>
        /// A <see cref="T:System.Collections.Generic.IEnumerator`1"/> that can be used to iterate through the collection.
        /// </returns>
        /// <filterpriority>1</filterpriority>
        public abstract IEnumerator<int> GetEnumerator();

        /// <summary>
        /// Returns an enumerator that iterates through a collection.
        /// </summary>
        /// <returns>
        /// An <see cref="T:System.Collections.IEnumerator"/> object that can be used to iterate through the collection.
        /// </returns>
        /// <filterpriority>2</filterpriority>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        #region Implementation of ITree<int>

        /// <summary>
        /// Returns the item for the index i.
        /// </summary>
        /// <param name="index">
        /// The index.
        /// </param>
        /// <returns>
        /// The item for the index i.
        /// </returns>
        public abstract int GetItem(int index);

        /// <summary>
        /// Returns a snapshot of the tree, if the tree isn't already a snapshot itself. Else it will throw an exception!
        /// </summary>
        /// <returns>
        /// A snapshot of the tree, if the tree isn't already a snapshot itself.
        /// </returns>
        public abstract ITree<int> Snapshot();

        #endregion

        #region Node

        /// <summary>
        /// A red black tree node.
        /// </summary>
        protected class BinaryTreeNode
        {
            /// <summary>
            /// Initializes a new instance of the <see cref="BinaryTreeNode"/> class. 
            /// </summary>
            /// <param name="item">
            /// The data item.
            /// </param>
            public BinaryTreeNode(int item)
            {
                Item = item;
            }

            /// <summary>
            /// Initializes a new instance of the <see cref="BinaryTreeNode"/> class.
            /// </summary>
            /// <param name="left">
            /// The left node.
            /// </param>
            /// <param name="item">
            /// The item.
            /// </param>
            /// <param name="right">
            /// The right node.
            /// </param>
            public BinaryTreeNode(BinaryTreeNode left, int item, BinaryTreeNode right)
            {
                Left = left;
                Item = item;
                Right = right;
            }

            /// <summary>
            /// Gets or sets left node.
            /// </summary>
            public BinaryTreeNode Left { get; set; }

            /// <summary>
            /// Gets or sets right node.
            /// </summary>
            public BinaryTreeNode Right { get; set; }

            /// <summary>
            /// Gets or sets the item.
            /// </summary>
            public int Item { get; set; }

            /// <summary>
            /// Returns a string replication of the node with its children.
            /// </summary>
            /// <returns>
            /// A string replication of the node with its children.
            /// </returns>
            public override string ToString()
            {
                return "[" + (Left == null ? "_" : Left.ToString()) + ","
                  + Item + "," + (Right == null ? "_" : Right.ToString()) + "]";
            }
        }

        #endregion
		
        #region TreeContract class

        /// <summary>
        /// Holds all contracts for the interface ITree
        /// </summary>
        [ContractClassFor(typeof(TreeBase))]
        internal abstract class TreeContract : TreeBase
        {
            #region Implementation of ICollection<int>

            /// <summary>
            /// Adds an item to the <see cref="T:System.Collections.Generic.ICollection`1"/>.
            /// </summary>
            /// <param name="item">The object to add to the <see cref="T:System.Collections.Generic.ICollection`1"/>.</param><exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.ICollection`1"/> is read-only.</exception>
            public override void Add(int item)
            {
                #region Code Contracs: Pre - and Post conditions

                Contract.Requires(!IsReadOnly);

                #endregion
            }

			public override void Clear()
			{
				#region Code Contracs: Pre - and Post conditions

				Contract.Requires(!IsReadOnly);

				#endregion
			}

            #endregion

            #region Implementation of ITree<int>

            /// <summary>
            /// Returns the item for the index i.
            /// </summary>
            /// <param name="index">
            /// The index.
            /// </param>
            /// <returns>
            /// The item for the index i.
            /// </returns>
            public override int GetItem(int index)
            {
                throw new NotImplementedException();
            }

            /// <summary>
            /// Returns a snapshot of the tree, if the tree isn't already a snapshot itself. Else it will throw an exception!
            /// </summary>
            /// <returns>
            /// A snapshot of the tree, if the tree isn't already a snapshot itself.
            /// </returns>
            public override ITree<int> Snapshot()
            {
                #region Code Contracs: Pre - and Post conditions

                Contract.Requires(!IsReadOnly);

                #endregion

                return default(ITree<int>);
            }

            #endregion
			
			#region ContractInvariantMethod

			// ReSharper disable UnusedMember.Local

			/// <summary>
			/// This method is used by code contracts to set all the invariants for the class.
			/// </summary>
			[ContractInvariantMethod]
			private void ObjectInvariant()
			{
				Contract.Invariant(ChangeStamp >= 0);
				Contract.Invariant(Count >= 0);
			}

			// ReSharper restore UnusedMember.Local
			#endregion
        }

        #endregion
    }
}